package com.jack.leetcode.eachproblem_2020;

public class 翻转对 {

    public int reversePairs(int[] nums) {
        if(nums.length == 0){
            return 0;
        }
        return reversePairMergeSort(nums, 0, nums.length - 1);
    }

    private int reversePairMergeSort(int[] nums, int left, int right){
        if(left == right){
            return 0;
        }else{
            int mid = (left + right) / 2;
            int n1 = reversePairMergeSort(nums, left, mid);
            int n2 = reversePairMergeSort(nums, mid + 1, right);
            int ret = n1 + n2;

            int i = left, j = mid + 1;
            while(i <= mid){
                while(j <= right && (long) nums[i] > 2 * (long) nums[j]){
                    j++;
                }
                ret += j - mid - 1;
                i++;
            }

            int[] sorted = new int[right - left + 1];
            int p1 = left, p2 = mid + 1, p = 0;
            while(p1 <= mid || p2 <= right){
                if(p1 > mid){
                    sorted[p++] = nums[p2++];
                }else if(p2 > right){
                    sorted[p++] = nums[p1++];
                }else{
                    sorted[p++] = nums[p1] > nums[p2] ? nums[p2++] : nums[p1++];
                }
            }
            for(int k = 0;k < sorted.length;k++){
                nums[k + left] = sorted[k];
            }

            return ret;
        }
    }
}
